package graph.digraph;

import linear.Stack;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 拓扑排序
 */
public class Topological {
    // 顶点拓扑排序
    private Stack<Integer> order;


    public Topological(Digraph G) {
        // 检查是否有环
        DirectedCycle directedCycle = new DirectedCycle(G);
        if (!directedCycle.hasCycle()) {
            // 进行继续深度的排序
            DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
            order = depthFirstOrder.reversePost();
        }

    }

    public boolean isCycle() {
        return order == null;
    }

    public Stack<Integer> order() {
        return order;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(DirectedCycle.class.getClassLoader().getResourceAsStream("road_find.txt")));
        int number = Integer.parseInt(reader.readLine());
        Digraph G = new Digraph(number);
        int roadNumber = Integer.parseInt(reader.readLine());
        // 循环读取道路，并调用addEdge方法
        for (int i = 0; i < roadNumber; i++) {
            String line = reader.readLine();
            int p = Integer.parseInt(line.split(" ")[0]);
            int q = Integer.parseInt(line.split(" ")[1]);
            G.addEdge(p, q);
        }
        // 创建测试对象
        Topological topological = new Topological(G);
        StringBuilder stringBuilder = new StringBuilder();
        for (Integer v : topological.order()) {
            stringBuilder.append(v).append(" -> ");
        }
        stringBuilder.deleteCharAt(stringBuilder.length() - 2);
        stringBuilder.deleteCharAt(stringBuilder.length() - 2);
        System.out.println(stringBuilder);
    }
}
